package solution.s_127;

import java.util.*;

/**
 * 解题思路：
 *      首先排除无法转换的情况。
 *      将所有数据想象成一张图，比如 ["hot","dot","dog","lot","log","cog"]，绘出的图如下：
 *          ```mermaid
 *          graph LR
 * 	            A((hit)) --- B((hot))
 * 	            B((hot)) --- C((dot))
 * 	            B((hot)) --- D((lot))
 * 	            C((dot)) --- D((lot))
 * 	            C((dot)) --- E((dog))
 * 	            D((lot)) --- F((log))
 * 	            E((dog)) --- F((log))
 * 	            E((dog)) --- G((cog))
 * 	            F((log)) --- G((cog))
 *          ```
 *      我们只需要从 beginWord 开始，使用广度优先遍历，最先访问到 endWord 的便是最短路径。
 */
public class Solution20201026 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 排除无法转换的情况
        if (! wordList.contains(endWord)) { return 0; }

        // 将开始节点加入到图中
        if (! wordList.contains(beginWord)) {
            wordList.add(beginWord);
        }
        // 先构建一张图
        Map<String, List<String>> map = constructMap(wordList);

        // 进行广度优先遍历
        int length = 0;
        // 已经遍历过的节点
        Set<String> set = new HashSet<>();
        // 本次需要遍历的节点
        List<String> curList = new ArrayList<>();
        curList.add(beginWord);

        while (! curList.isEmpty()) {
            // 下一次需要遍历的节点
            List<String> nextList = new ArrayList<>();

            for (String str : curList) {
                // 假如改节点已经遍历过，直接遍历下一个节点
                if (set.contains(str)) {
                    continue;
                }

                if (str.equals(endWord)) {
                    return length + 1;
                }

                // 将与当前元素连线的元素加入到下一次遍历的节点中
                nextList.addAll(map.get(str));
                // 将当前元素假如到已经遍历过的元素集中
                set.add(str);
            }

            // 遍历完一次，深度进行加 1
            length ++;
            curList = nextList;
        }

        // 假如最后都没有结果，说明无法到达
        return 0;
    }

    private Map<String, List<String>> constructMap(List<String> wordList) {
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < wordList.size(); i ++) {
            String str1 = wordList.get(i);

            // 保存与 str1 可以连线的点
            List<String> temp = new ArrayList<>();
            for (int j = 0; j < wordList.size(); j ++) {
                // 如果两个元素相等，直接进行下一次比较
                if (i == j) { continue; }

                String str2 = wordList.get(j);

                // 比较两个元素是否满足只有一个字符不同
                if (meetTheConditions(str1, str2)) {
                    temp.add(str2);
                }
            }

            // 保存图
            map.put(str1, temp);
        }

        return map;
    }

    private boolean meetTheConditions(String str1, String str2) {
        int count = 0;
        for (int i = 0; i < str1.length(); i ++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                count ++;
                // 不相等字符超过 1，返回 false
                if (count > 1) { return false; }
            }
        }

        return count == 1;
    }
}
